package lists;

import java.util.Comparator;
import java.util.Iterator;
import java.util.RandomAccess;

public class MyCollections {
	public static <T extends Comparable<T>> void sort(MyList<T> list) {
		if (list == null) {
			throw new NullPointerException();
		}
		if (list.size() < 2) {
			return;
		}
		if (list instanceof RandomAccess) {

			quickSortStep(list, 0, list.size() - 1);

		} else {
			insertionSort(list);
		}
	}

	public static <T> void sort(MyList<T> list, Comparator<T> c) {
		if (list == null) {
			throw new NullPointerException();
		}
		if (list.size() < 2) {
			return;
		}
		if (list instanceof RandomAccess) {

			quickSortStep(list, c, 0, list.size() - 1);

		} else {
			insertionSort(list, c);
		}
	}

	private static <T extends Comparable<T>> void insertionSort(MyList<T> list) {
		for (int i = 0; i < list.size(); i++) {
			T elem = list.get(i);
			int j = i;
			while (j > 0 && (elem.compareTo(list.get(j - 1)) < 0)) {
				swap(list, j, j - 1);
				j--;
			}

		}
	}

	private static <T> void insertionSort(MyList<T> list, Comparator<T> c) {
		for (int i = 0; i < list.size(); i++) {
			T elem = list.get(i);
			int j = i;
			while (j > 0 && (c.compare(elem, list.get(j - 1)) < 0)) {
				swap(list, j, j - 1);
				j--;
			}

		}
	}

	private static <T extends Comparable<T>> void quickSortStep(MyList<T> list,
			int leftBound, int rightBound) {
		int i = leftBound;
		int j = rightBound;
		int pivot = (leftBound + ((rightBound - leftBound) / 2));

		while (i <= j) {

			while (list.get(i).compareTo(list.get(pivot)) < 0) {
				i++;
			}
			while (list.get(j).compareTo(list.get(pivot)) > 0) {
				j--;
			}
			if (i <= j) {
				swap(list, i, j);
				i++;
				j--;
			}
		}
		if (leftBound < j) {
			quickSortStep(list, leftBound, j);
		}
		if (i < rightBound) {
			quickSortStep(list, i, rightBound);
		}
	}

	private static <T> void quickSortStep(MyList<T> list, Comparator<T> c,
			int leftBound, int rightBound) {
		int i = leftBound;
		int j = rightBound;
		int pivot = (leftBound + ((rightBound - leftBound) / 2));

		while (i <= j) {

			while (c.compare(list.get(i), (list.get(pivot))) < 0) {
				i++;
			}
			while (c.compare(list.get(j), (list.get(pivot))) > 0) {
				j--;
			}
			if (i <= j) {
				swap(list, i, j);
				i++;
				j--;
			}
		}
		if (leftBound < j) {
			quickSortStep(list, c, leftBound, j);
		}
		if (i < rightBound) {
			quickSortStep(list, c, i, rightBound);
		}
	}

	public static <T> void swap(MyList<T> list, int i, int j) {
		T element1 = list.get(i);
		T element2 = list.get(j);
		list.set(i, element2);
		list.set(j, element1);
	}

	public static <T> void copy(MyList<T> dest, MyList<T> src) {
		Iterator<T> iterSrc = src.iterator();
		while (iterSrc.hasNext()) {
			dest.add(iterSrc.next());
		}
	}

	public static <T> void reverse(MyList<T> list) {
		for (int i = 0, j = list.size() - 1; i <= j; i++, j--) {
			swap(list, i, j);
		}
	}

	public static <Type extends Comparable<Type>, T extends RandomAccess & MyList<Type>> int binarySearch(
			T list, Type key) {
		int lo = 0, hi = list.size() - 1;
		int insertionPoint = 0;

		while (lo <= hi) {

			int mid = lo + ((hi - lo) / 2);

			if (key.compareTo(list.get(mid)) < 0) {

				hi = mid - 1;
			} else {
				if (key.compareTo(list.get(mid)) > 0) {

					lo = mid + 1;
				} else {
					return mid;
				}
			}
		}

		insertionPoint = lo;

		return (-(insertionPoint) - 1);
	}
}
